package com.yeung.swordoffer;

import java.util.ArrayList;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
 * 要求不能创建任何新的结点，只能调整树中结点指针的指向。
 */
public class 二叉搜索树与双向链表 {
    public TreeNode Convert2(TreeNode pRootOfTree) {
        return convert(pRootOfTree);
    }

    /**
     * 方法一, 拼接链表
     *
     * @param pRootOfTree
     * @return
     */
    public static TreeNode convert(TreeNode pRootOfTree) {
        //搜索树的特点, 左子树小于根节点,根节点小于右子树(中序遍历,即可有序)
        if (pRootOfTree == null) return null;
   /*     if (pRootOfTree.left == null && pRootOfTree.right == null)
            return pRootOfTree;*/
        //中序递归遍历
        TreeNode lch = convert(pRootOfTree.left);
        TreeNode tmp = lch;
        //将左子树的最后一个右节点作为根的左节点,(关系相互)
        if (lch != null) {
            //定位到左子树的最后一个右节点
            while (tmp.right != null)
                tmp = tmp.right;
            tmp.right = pRootOfTree;
            pRootOfTree.left = tmp;
        }
        //将右子树的最左节点拼接到根节点后边
        TreeNode rch = convert(pRootOfTree.right);
        //如果右子树链表不为空的话，将该链表追加到root节点之后
        if (rch != null) {
            rch.left = pRootOfTree;
            pRootOfTree.right = rch;
        }
        return lch != null ? lch : pRootOfTree;//左子树不为空,将 左子树的最左节点作为头节点
    }

    /**
     * 方法2
     * 利用中序遍历整个树, 顺序记录下来,然后遍历list改指针
     *
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        ArrayList<TreeNode> list = new ArrayList<>();
        Convert(pRootOfTree, list);
        return Convert(list);

    }

    //中序遍历，在list中按遍历顺序保存
    public void Convert(TreeNode pRootOfTree, ArrayList<TreeNode> list) {
        if (pRootOfTree.left != null) {
            Convert(pRootOfTree.left, list);
        }

        list.add(pRootOfTree);

        if (pRootOfTree.right != null) {
            Convert(pRootOfTree.right, list);
        }
    }

    //遍历list，修改指针
    public TreeNode Convert(ArrayList<TreeNode> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).right = list.get(i + 1);
            list.get(i + 1).left = list.get(i);
        }
        return list.get(0);
    }
}
